package org.example.myleet.p1600;

import java.util.*;

public class ThroneInheritance {

    static class TreeNode {

        String name;

        List<TreeNode> children;

        boolean alive;

        public TreeNode(String name) {
            this.name = name;
            children = new ArrayList<>();
            alive = true;
        }
    }

    private Map<String, TreeNode> nameNodeMap;

    private int memberLen;

    private TreeNode root;

    public ThroneInheritance(String kingName) {
        root = new TreeNode(kingName);
        nameNodeMap = new HashMap<>();
        nameNodeMap.put(kingName, root);
        memberLen = 1;
    }

    public void birth(String parentName, String childName) {
        TreeNode member = nameNodeMap.get(parentName);
        TreeNode child = new TreeNode(childName);
        member.children.add(child);
        nameNodeMap.put(childName, child);
        ++memberLen;
    }

    public void death(String name) {
        TreeNode member = nameNodeMap.get(name);
        member.alive = false;
        --memberLen;
    }

    /**
     * 嫡长子继位，中序遍历
     */
    public List<String> getInheritanceOrder() {
        List<String> result = new ArrayList<>(memberLen);
        if (root.alive) {
            result.add(root.name);
        }
        Deque<TreeNode> stack = new LinkedList<>();
        for (int i = root.children.size() - 1; i > -1; --i) {
            stack.push(root.children.get(i));
        }
        while (!stack.isEmpty()) {
            TreeNode member = stack.pop();
            if (member.alive) {
                result.add(member.name);
            }
            if (member.children.size() > 0) {
                for (int i = member.children.size() - 1; i > -1; --i) {
                    stack.push(member.children.get(i));
                }
            }
        }
        return result;
    }
}
